The present invention relates to an improved method and system for estimating wire length values for an integrated circuit.
An integrated circuit (“IC”) is a semiconductor device that includes many electronic components (e.g., transistors, resistors, diodes, etc.). These components are often interconnected to form multiple circuit components (e.g., gates, cells, memory units, arithmetic units, controllers, decoders, etc.) on the IC. The electronic and circuit components of IC's are jointly referred to below as “components.”
An IC also includes multiple layers of metal and/or polysilicon wiring (collectively referred to below as “metal layers”) that interconnect its electronic and circuit components. For instance, many IC's are currently fabricated with five to seven metal layers. In theory, the wiring on the metal layers can be all-angle wiring (i.e., the wiring can be in any arbitrary direction). Such all-angle wiring is commonly referred to as Euclidean wiring. In practice, however, each metal layer typically has a preferred wiring direction, and the preferred direction alternates between successive metal layers. Many IC's use the Manhattan wiring model, which specifies alternating layers of preferred-direction horizontal and vertical wiring. In this wiring model, the majority of the wires can only make 90 degree turns. However, occasional diagonal jogs are sometimes allowed on the preferred horizontal and vertical layers. Design engineers design IC's by transforming circuit description of the IC's into geometric descriptions, called layouts. To create layouts, design engineers typically use electronic design automation (“EDA”) tools. These tools provide sets of computer-based applications for creating, editing, and analyzing IC design layouts.
IC's can also be fabricated with diagonal interconnect lines (i.e., diagonal wiring). In some of these embodiments, the IC layouts not only have diagonal interconnect lines, but also have horizontal and vertical interconnect lines. As used in this document, an interconnect line is “diagonal” if it forms an angle other than zero or ninety degrees with respect to one of the sides of the layout boundary. On the other hand, an interconnect line is “horizontal” or “vertical” if it forms an angle of 0 degree or 90 degree with respect to one of the sides of the layout.
FIG. 1 illustrates the wiring architecture (i.e., the interconnect-line architecture) of an IC layout 700 that utilizes horizontal, vertical, and 45 degrees diagonal interconnect lines. In this document, this architecture is referred to as the octagonal wiring model, in order to convey that an interconnect line can traverse in eight separate directions from any given point.
The horizontal lines 705 are the lines that are parallel (i.e., are at 0 degrees) to the x-axis, which is defined to be parallel to the width 710 of the layout. The vertical lines 715 are parallel to the y-axis, which is defined to be parallel to the height 720 of the layout. In other words, the vertical interconnect lines 715 are perpendicular (i.e., are at 90 degrees) to the width of the IC layout. In this architecture, one set 725 of diagonal lines are at +45 degrees with respect to the width of the IC layout, while another set 730 are at −45 degrees with respect to the width of the IC layout.
FIG. 2 illustrates one manner of implementing the wiring architecture illustrated in FIG. 1 on an IC. Specifically, FIG. 2 illustrates five metal layers for an IC. The first three layers 805–815 are Manhattan layers. In other words, the preferred direction for the wiring in these layers is either the horizontal direction or the vertical direction. The preferred wiring direction in the first three layers typically alternates so that no two consecutive layers have the same direction wiring. However, in some cases, the wiring in consecutive layers is in the same direction.
The next two layers 820 and 825 are diagonal layers. The preferred direction for the wiring in the diagonal layers is +/−45 degrees. Also, as in the first three layers, the wiring directions in the fourth and fifth layer are typically orthogonal (i.e., one layer is +45 degrees and the other is −45 degrees), although they do not have to be.
Even though some embodiments of the invention are described below to work with IC layouts that utilize the above-described octagonal wiring model, one of ordinary skill will understand that the invention can be used with any wiring model. For instance, the invention can be used with wiring architectures that are strictly diagonal (i.e., that do not have horizontal and vertical preferred direction wiring).
Also, some embodiments are used with non-45 degrees diagonal wiring. For example, some embodiments are used with IC layouts that have horizontal, vertical, +/−60 degrees, and/or +/−120 degrees diagonal interconnect lines.
EDA tools create layouts by using geometric shapes that represent different materials and devices on IC's. For instance, EDA tools commonly use rectangular lines to represent the wire segments that interconnect the IC components. These tools also represent electronic and circuit IC components as geometric objects with varying shapes and sizes. For the sake of simplifying the discussion, these geometric objects are shown as rectangular blocks in this document.
A net is typically defined as a collection of pins that need to be electrically connected. A list of all or some of the nets in a layout is referred to as a net list. In other words, a net list specifies a group of nets, which, in turn, specify the interconnections between a set of pins.
Placement is a key operation in the physical design cycle. It is the process of arranging the circuit modules on a layout, in order to achieve certain objectives, such as reducing layout area, wirelength, wire congestion, etc. A poor placement configuration not only can consume a large area, but it also can make routing difficult and result in poor performance.
Numerous EDA placers have been proposed to date. Certain placers are constrained-optimization placers, which (1) use cost-calculating functions to generate placement scores (i.e., placement costs) that quantify the quality of placement configurations, and (2) use optimization algorithms to modify iteratively the placement configurations to improve the placement scores generated by the cost-calculating functions.
A constrained-optimization placer typically receives (1) a list of circuit modules, (2) an initial placement configuration for these modules, and (3) a net list that specifies the interconnections between the modules. The initial placement configuration can be random (i.e., all the modules can be positioned randomly). Alternatively, the initial configuration can be partially or completely specified by a previous physical-design operation, such as the floor planning.
A constrained-optimization placer then uses a cost-calculating function to measure the quality of the initial placement configuration. The cost function generates a metric score that is indicative of the placement quality. Different cost-calculating functions measure different placement metrics. For instance, as further described below, some functions measure wirelength (e.g., measure each net's minimum spanning tree, Steiner tree, or bounding-box perimeter, etc.), while others measure congestion (e.g., measure number of nets intersected by cut lines).
After calculating the metric cost of the initial placement configuration, a constrained-optimization placer uses an optimization algorithm to modify iteratively the placement configuration to improve the placement score generated by its cost-calculating function. Different optimization techniques modify the placement configuration differently. For instance, at each iteration, some techniques move one circuit module, others swap two modules, and yet others move a number of related modules. Also, at each iteration, some optimization techniques (e.g., KLFM and tabu search algorithms) search for the best move, while others (e.g., simulated annealing and local optimization) select random moves. In addition, some techniques (e.g., simulated annealing) accept moves that make the metric score worse, whereas others (e.g., local optimization) do not.
One type of constrained-optimization placement techniques is the semi-perimeter method. The semi-perimeter method is a cost-calculating function used by some constrained-optimization techniques. This method quickly generates an estimate of the wirelength cost of a placement. For each net, this method typically (1) finds the smallest bounding-box that encloses all the net's pins, and (2) computes half the perimeter of this bounding rectangle.
FIG. 3 illustrates a rectangular bounding box 300 for a net that contains pins 302, 304, 306, 308, 310, 312, and 314. The computed semi-perimeter value of this box 300 equals the sum of its width x and height y. This computed semi-perimeter value provides a lower bound estimate on the amount of wire required to route a net. A bounding box with a diagonal attribute can also be used to estimate wirelength cost. U.S. Pat. No. 6,671,864 describes one example approach for using a bounding box with a diagonal attribute to estimate a wirelength cost for placement, and is incorporated herein by reference in its entirety.
The semi-perimeter method sums the semi-perimeter values of all the bounding rectangles of all the nets to obtain an estimated wirelength cost for a placement configuration. An optimization technique can then be used to modify iteratively the placement configuration to reduce this wirelength cost estimate, and thereby obtain an acceptable placement configuration.
Methods and systems for specifying an analytical wirelength formulation that is continuous along with its derivative are disclosed in co-pending U.S. application Ser. No. 11/026,511, entitled “Method and System for Implementing an Analytical Wirelength Formulation”, filed on even date herewith, which is hereby incorporated by reference in its entirety. The approach performs a wirelength estimate estimation in which a continuous formulation is employed to identify and use a bounding box to enclose circuit elements of a net, and in which an attribute of the bounding box may be completely or partially diagonal. Such formulations are used for optimizing the wirelength using numerical approaches. In addition, embodiments of the invention specifies a wirelength formulation based upon layer availability.
Referring back to FIG. 2, consider if one or more of the metal layers are unavailable, which means that one or more routing directions may be unavailable. This presents an additional challenge to determining an estimated wirelength since the unavailability of one or more routing directions will affect the shape and character of the bounding box that is used to enclose the circuit elements.
Embodiments of the invention provide methods and systems for formulating a wirelength estimate that takes into account whether any of the routing directions are unavailable. Under certain circumstances, one or more of the routing layers may not be available for routing a wire. If this occurs, then the bounding box that is determined for performing the wirelength estimate would likely take into account the unavailability of the layer.
Other and additional objects, features, and advantages of the invention are described in the detailed description, figures, and claims.